public class Darr implements StoreEngine {
    private Object [] data = null;
    private int length = 0;
    private int travelId = 0;
    static final private Darr findArr = new Darr();

    public Darr() {}

    //构造方法，支持构造传入数据
    public Darr(Object ... newData) {
        append(newData);
    }

    //尾插数据
    public StoreEngine append(Object ... newData) {
        return add(length + 1, newData);
    }

    //头插数据
    public StoreEngine prepend(Object ... newData) {
        return add(1, newData);
    }

    //指定位置插入数据
    public StoreEngine add(int index, Object ... inputData) {
        //如果没有传入新数据，则不做任何操作
        if (inputData == null)
            return this;

        if (index < 1)
            index = 1;
        else if (index > length)
            index = length + 1;

        Object [] newData = new Object[length + inputData.length];
        if (data != null) {
            System.arraycopy(data, 0, newData, 0, index - 1);
            System.arraycopy(inputData, 0, newData, index - 1, inputData.length);

            System.arraycopy(data, index - 1,
                                newData, index + inputData.length - 1,
                                data.length - index + 1);
        } else {
            System.arraycopy(inputData, 0, newData, 0, inputData.length);
        }

        length += inputData.length;
        data = newData;

        return this;
    }

    //返回数据个数
    public int len() {
        return length;
    }

    // 返回第几个数据
    public Object find(int index) {
        return (index < 1 || index > length) ? null : data[index - 1];
    }

    public Object first() {
        return (length > 0) ? data[0] : null;
    }

    public Object last() {
        return (length > 0) ? data[length - 1] : null;
    }

    // 返回指定起始位置开始查找，并且指定返回查找到的结果个数
    public StoreEngine find(int start, int num, Object key, DataCompare cmpObj) {

        findArr.clean();

        for (int i = start; i < length; ++i) {
            if (cmpObj.compare(key, data[i]) == 0) {
                findArr.append(data[i]);
                if (num != 0 && --num == 0) {
                    break;
                }
            }
        }
        return findArr;
    }

    // 返回查找到的第几个数据
    public Object findOf(int index, Object key, DataCompare cmpObj) {
        find(0, index, key, cmpObj);
        if (findArr.len() < index)
            return null;
        return findArr.last();
    }

    // 返回查找到的前几个数据
    public StoreEngine findNum(int num, Object key, DataCompare cmpObj) {
        return find(0, num, key, cmpObj);
    }

    // 返回查找到所有数据
    public StoreEngine findAll(Object key, DataCompare cmpObj) {
        return find(0, 0, key, cmpObj);
    }

    //根据查找数据返回对应数据的下标, index控制返回第几个查找的数据下标
    //index < 0 从后向前查，返回对应第几个查找到的数据下标
    //index > 0 从前向后查，返回对应第几个查找到的数据下标
    //index = 0 从前向后查，返回最后一个查找到的数据下标
    public int findInd(int index, Object key, DataCompare cmpObj) {
        int dataInd = -1;

        if (index < 0) {

            index *= -1;

            for (int i = length - 1; i >= 0; --i) {
                if (cmpObj.compare(key, data[i]) == 0) {
                    dataInd = i;
                    if (--index == 0)
                        break;
                }
            }
        } else {
            for (int i = 0; i < length; ++i) {
                if (cmpObj.compare(key, data[i]) == 0) {
                    dataInd = i;
                    if (index != 0 && --index == 0)
                        break;
                }
            }
        }

        return dataInd;
    }

    //对数据进行排序
    public StoreEngine sort(DataCompare cmpObj) {
        int i, j, m, ind;
        Object tmpData;

        for (i = 0, m = length - 1; i < m; ++i) {
            ind = i;
            tmpData = data[i];
            for (j = i + 1; j < length; ++j) {
                if (cmpObj.compare(data[j], tmpData) > 0) {
                    tmpData = data[j];
                    ind = j;
                }
            }
            data[ind] = data[i];
            data[i] = tmpData;
        }

        return this;
    }

    //删除第几个数据
    public StoreEngine delete(int index) {
        if (index < 1 || index > length)
            return this;

        Object [] newData = new Object[length - 1];
        System.arraycopy(data, 0, newData, 0, index - 1);
        System.arraycopy(data, index, newData, index - 1, length - index);
        length--;
        data = newData;

        return this;
    }

    //删除查找到数据指定删除从第几个到多少个
    public StoreEngine delete(int start, int num, Object key, DataCompare cmpObj) {
        for (int i = start; i < length; ++i) {
            if (cmpObj.compare(key, data[i]) == 0) {
                // System.out.printf("=====> delet index = %d\n", i);
                delete(i-- + 1);
                if (num != 0 && --num == 0)
                    break;
            }
        }

        return this;
    }
    // 删除查找到的第几个数据
    public StoreEngine deleteOf(int index, Object key, DataCompare cmp) {
        return delete(findInd(index, key, cmp));
    }

    //删除指定个数查找到的数据
    public StoreEngine deleteNum(int num, Object key, DataCompare cmp) {
        return delete(0, num, key, cmp);
    }

    public StoreEngine deleteAll(Object key, DataCompare cmp) {
        return delete(0, 0, key, cmp);
    }

    // 清空所有数据
    public StoreEngine clean() {
        data = null;
        length = 0;
        travelId = 0;
        return this;
    }

    // 遍历接口
    // 实现重置遍历标识
    public StoreEngine rewind() {
        travelId = 0;
        return this;
    }

    // 返回下一个数据元素
    public Object getNext() {
        if (travelId == length) {
            travelId = 0;
            return null;
        }
        return data[travelId++];
    }
}
